/**
 *有 n名工人。给定两个数组quality和wage，其中，quality[i]表示第i名工人的工作质量，其最低期望工资为wage[i]。
 *
 * 现在我们想雇佣k名工人组成一个工资组。在雇佣一组 k名工人时，我们必须按照下述规则向他们支付工资：
 *
 * 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
 * 工资组中的每名工人至少应当得到他们的最低期望工资。
 * 给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额。在实际答案的10-5以内的答案将被接受。。
 *
 * 链接：https://leetcode.cn/problems/minimum-cost-to-hire-k-workers
 */

/**
 * 思路：
 * 堆（优先队列）
 * 我们可以定义一个“价值”，表示工人最低期望工资与工作质量之比。例如某位工人的最低期望工资为 100，工作质量为 20，那么他的价值为 100 / 20 = 5.0。
 *
 * 可以发现，如果一名工人的价值为 R，当他恰好拿到最低期望工资时，如果所有价值高于 R 的工人都无法拿到最低期望工资，而所有价值低于 R 的工人都拿得比最低期望工资多。
 * 因此，我们可以按照这些工人的价值，对他们进行升序排序。排序后的第 i 名工人可以在它之前选 K - 1 名工人(因为在k-1名工人一定能拿到得比最低期望工资多)
 * 并计算对应的工资总和，为 R * sum(quality[c1] + quality[c2] + … + quality[c{k-1}] + quality[i])，也就是说，我们需要在前 i 名工人中选择 K 个工作质量最低的。我们可以使用一个大根堆来实时维护 K 个最小值。
 *
 *
 * 那么当我们以某一个工人 x 作为一个工资组中权重最高时，工资组中其他人员只需要在权重小于工人 x 的集合中选择工作质量最少的 k−1 名工人来组成工资组即可，
 * 此时便能达到以工人 x 为权重最高的工资组的总工作量最小，从而达到以工人 x 为权重最高的工资组的最小工资开销。然后我们枚举以每一个能成为工资组中权重最大的工人来计算最小工资组开销，
 * 然后取其中的最小即可。在处理的过程中，我们可以先将工人按照权重进行升序排序，然后在遍历过程中可以用优先队列来维护之前工作质量最少的 k−1 名工人。

 * 链接：https://leetcode.cn/problems/minimum-cost-to-hire-k-workers/solution/gu-yong-k-ming-gong-ren-de-zui-di-cheng-rsz3t/
 */

class MincostToHireWorkers {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n=quality.length;
        Integer[] h=new Integer[n];
        for(int i=0;i<n;i++) {
            h[i]=i;
        }
        Arrays.sort(h,(a,b)->{
            return quality[b]*wage[a]-quality[a]*wage[b];
        });
        double res=1e9;
        double totalq=0.0;//k名工人要完成工作的总重量
        PriorityQueue<Integer> qu=new PriorityQueue<Integer>((a,b)->b-a);
        for(int i=0;i<k-1;i++) {//因为已经对h[i]升序，所以现在前k-1个工人一定能拿到比期望工资还要多的钱，所以我们只要遍历剩下的工人，然后选在剩下的工人中选第k个工人去保证总金额最少就行，这个最大堆就是用来维护k个最小值
            totalq+=quality[h[i]];
            qu.offer(quality[h[i]]);
        }
        for(int i=k-1;i<n;i++) {//从剩下的工人中选第k名工人，要是选了之后，总工资减少，就更新总工资的值
            int idx=h[i];
            totalq+=quality[idx];
            qu.offer(quality[idx]);
            double totalc=((double)wage[idx]/quality[idx]*totalq);//当从剩下的工人中选第k个工人时的总工资
            res=Math.min(res,totalc);//与当前总工资相比，取最小总工资
            totalq-=qu.poll();
        }
        return res;
    }
}